package main.graph;

import java.util.ArrayList;
import java.util.Collection;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.TreeSet;

import main.model.Relationship;

import y.algo.ShortestPaths;
import y.algo.SpanningTrees;
import y.base.DataProvider;
import y.base.Edge;
import y.base.EdgeCursor;
import y.base.EdgeList;
import y.base.EdgeMap;
import y.base.Node;
import y.base.NodeCursor;
import y.base.YCursor;
import y.base.YList;

/**
 * some graph algorithms are developed here including all shortest paths, all
 * MST, and all Steiner trees
 * 
 * @author YuanAn
 * 
 */
public class GraphAlgo {

	/**
	 * compute all the shortest paths between two nodes.
	 */
	public static ArrayList<EdgeList> allShortestPathsBetween(ValuedGraph graph, Node startNode,
			Node endNode, EdgeMap edgeCostsDP) {

		// To hold an edge list for every path.
		ArrayList<EdgeList> allShortestPaths = new ArrayList<EdgeList>();

		// The actual number of proper shortest paths is unknown, so we start
		// with a really great value for 'k'.
		YCursor pathCursor = ShortestPaths.kShortestPathsCursor(graph,
				edgeCostsDP, startNode, endNode, Integer.MAX_VALUE);
		if (pathCursor.ok()) {
			// The first path between the two nodes having least costs.
			final EdgeList firstPath = (EdgeList) pathCursor.current();
			final double costsOfFirstPath = calculateCostsForPath(firstPath,
					edgeCostsDP);

			allShortestPaths.add(firstPath);
			pathCursor.next();

			// Look further.
			while (pathCursor.ok()) {
				EdgeList currPath = (EdgeList) pathCursor.current();
				double currCosts = calculateCostsForPath(currPath, edgeCostsDP);
				// If the current path is also a proper shortest path with costs
				// equal to those
				// of the first path, then add it to the list.
				if (!(currCosts > costsOfFirstPath)) {
					allShortestPaths.add(currPath);
					pathCursor.next();
				} else
					break;
			}
		}

		return allShortestPaths;
	}

	private static double calculateCostsForPath(EdgeList path, EdgeMap costs) {

		double ans = 0.0;

		for (EdgeCursor ec = path.edges(); ec.ok(); ec.next()) {
			Edge edge = ec.edge();
			ans += costs.getDouble(edge);

		}

		return ans;
	}
	
	/**
	 * find all the shortest paths from the start to the  nodes in set of terminals.
	 * 
	 * @param graph
	 * @param start
	 * @param terminals
	 * @param costs
	 * @return
	 */
	public static HashMap<Node, ArrayList<EdgeList>> allShortestPaths(ValuedGraph graph, Node start, Collection<Node> terminals, 
			EdgeMap costs){
		
		HashMap<Node,  ArrayList<EdgeList>> ans = new HashMap<Node, ArrayList<EdgeList>>();
		
		//for the source itself
		ArrayList<EdgeList> empty = new ArrayList<EdgeList>();
		ans.put(start, empty);
		
		Iterator<Node> nodeit = terminals.iterator();
		while(nodeit.hasNext()){
			Node terminal = nodeit.next();
			ArrayList<EdgeList> paths = allShortestPathsBetween(graph, start, terminal, costs);
			ans.put(terminal, paths);
		}
		
		
		return ans;
	}
	

	/**
	 * return all minimum spanning trees
	 * 
	 * @param graph
	 * @return
	 */
	public static ArrayList<EdgeList> allMSTs(ValuedGraph graph, EdgeMap weights) {

		ArrayList<EdgeList> allMsts = new ArrayList<EdgeList>();

		System.out.println("Starting allMSTs.");

		// find the first MST
		EdgeList rootMST = SpanningTrees.kruskal(graph, weights);
		allMsts.add(rootMST);

		// maintain a queue
		LinkedList<EdgeList> queue = new LinkedList<EdgeList>();
		queue.addLast(rootMST);
		int count = 0;
		while (!queue.isEmpty()) {
			count++;
			System.out.println("exchange to make " + count
					+ " th queue element." + " queue size: " + queue.size());
			EdgeList head = queue.removeFirst();
			EdgeList nonTreeEdges = findOkNonTreeEdges(graph, weights, head);
			// exchange a non tree edges with the edge in the cycle
			// which has same weight.
			// System.out.println("The number of nonTreeEdges:"+nonTreeEdges.size());
			// System.out.println((Edge)nonTreeEdges.get(0));
			for (EdgeCursor ec = nonTreeEdges.edges(); ec.ok(); ec.next()) {
				Edge f = ec.edge();
				EdgeList cycleEdges = findCycleEdges(graph, weights, head, f);
				// System.out.println("The number of cycleEdges:"+cycleEdges.size());
				for (EdgeCursor cycleEc = cycleEdges.edges(); cycleEc.ok(); cycleEc
						.next()) {
					Edge e = cycleEc.edge();
					EdgeList child = new EdgeList();
					child.add(f);
					for (EdgeCursor headEc = head.edges(); headEc.ok(); headEc
							.next()) {
						Edge parentEdge = headEc.edge();
						if (parentEdge != e)
							child.add(parentEdge);
					}
					if (!containsMST(allMsts, child)) {
						allMsts.add(child);
						queue.addLast(child);
						
						if(allMsts.size() >= 1000)
							return allMsts;
					}
				} // exchange(e,f)
			} // for each nonTreeEdge
		}

		return allMsts;
	}

	/**
	 * find the non tree edges whose weights are not greater than the maximum
	 * weight in the MST.
	 * 
	 * @param graph
	 * @param weights
	 * @param mst
	 * @return
	 */
	private static EdgeList findOkNonTreeEdges(ValuedGraph g, EdgeMap weights,
			EdgeList mst) {

		EdgeList result = new EdgeList();

		// the maximum weight in the MST
		double maxW = 0;
		for (EdgeCursor ec = mst.edges(); ec.ok(); ec.next()) {
			Edge e = ec.edge();
			if (weights.getDouble(e) > maxW)
				maxW = weights.getDouble(e);
		}

		for (EdgeCursor ec = g.edges(); ec.ok(); ec.next()) {
			Edge e = ec.edge();
			if (!mst.contains(e) && weights.getDouble(e) <= maxW)
				result.add(e);
		}

		EdgeComparator eComp = new EdgeComparator(weights);

		result.sort(eComp);

		return result;
	}

	/**
	 * find the edges in the cycle in the MST with f; the weights of those edges
	 * are the same as the weight of f.
	 * 
	 * @param g
	 * @param weights
	 * @param mst
	 * @param f
	 * @return
	 */
	private static EdgeList findCycleEdges(ValuedGraph g, EdgeMap weights,
			EdgeList mst, Edge f) {
		EdgeList tempResult = new EdgeList();

		Node v1 = f.source();
		Node v2 = f.target();
		EdgeMap visited = g.createEdgeMap();
		// set edges in the MST not visited; other edges are
		// set to visited.
		for (EdgeCursor ec = g.edges(); ec.ok(); ec.next()) {
			Edge e = ec.edge();
			if (!mst.contains(e))
				visited.setBool(e, true);
			else
				visited.setBool(e, false);
		}

		boolean[] foundCycle = { false };

		findCycleEdgesFromNode(g, weights, mst, v1, v2, tempResult, visited,
				foundCycle);

		// remove those edges with different weights from f
		EdgeList result = new EdgeList();
		// System.out.println("The size of tempResult:"+tempResult.size());
		for (EdgeCursor ec = tempResult.edges(); ec.ok(); ec.next()) {
			Edge e = ec.edge();
			if (weights.getInt(e) == weights.getInt(f))
				result.add(e);
		}

		return result;
	}

	private static void findCycleEdgesFromNode(ValuedGraph g, EdgeMap weights,
			EdgeList mst, Node source, Node target, EdgeList cycle,
			EdgeMap visited, boolean[] foundCycle) {

		if (foundCycle[0] == true)
			return;

		boolean leaf = true;

		for (EdgeCursor ec = source.edges(); ec.ok(); ec.next()) {
			Edge e = ec.edge();
			if (!visited.getBool(e) && !foundCycle[0]) {
				leaf = false;
				visited.setBool(e, true);
				cycle.add(e);
				Node otherEnd = e.opposite(source);
				if (otherEnd == target) {
					foundCycle[0] = true;
					break;
				}
				findCycleEdgesFromNode(g, weights, mst, otherEnd, target,
						cycle, visited, foundCycle);
			} // is visited?
		}
		if (leaf) // remove the last added edge.
			cycle.remove(cycle.size() - 1);
		else if (!foundCycle[0] && !cycle.isEmpty())
			// exhausted all neighboring edges, remove the last.
			cycle.remove(cycle.size() - 1);
	}

	/**
	 * test whether the MST has been generated.
	 * 
	 */
	private static boolean containsMST(ArrayList<EdgeList> msts, EdgeList mst) {

		boolean ans = false;

		for (int i = 0; i < msts.size(); i++) {
			EdgeList MST = msts.get(i);
			if (sameMSTs(MST, mst)) {
				ans = true;
				break;
			}
		}

		return ans;
	}

	/**
	 * test whether two MSTs are same one.
	 * 
	 */
	private static boolean sameMSTs(EdgeList first, EdgeList second) {

		for (EdgeCursor ec = first.edges(); ec.ok(); ec.next()) {
			Edge e = ec.edge();
			if (!second.contains(e)) {
				return false;
			}
		}

		for (EdgeCursor ec = second.edges(); ec.ok(); ec.next()) {
			Edge e = ec.edge();
			if (!first.contains(e)) {
				return false;
			}
		}

		return true;
	}

	
	/**
	 * get all Steiner trees by the set of fixed nodes: using an efficient algorithm by
	 * creating a single neighborhood graph by incorporating all the shortest paths
	 * 
	 * @param Graph
	 *            g
	 * @param EdgeMap
	 *            weights
	 * @param ArrayList
	 *            fixed
	 * @return a list of EdgeList each of which represents a Steiner tree
	 */
	public static ArrayList<EdgeList> allSteinerTreesIntegrated(ValuedGraph g, EdgeMap weights,
			Collection<Node> fixed) {

		ArrayList<EdgeList> result = new ArrayList<EdgeList>();
		
		if (fixed.isEmpty() || fixed.size() == 1)
			return result;
		else {
			
			//get all the integrated neighborhood graph
			ValuedGraph neighborhood = neighborhoodGraphIntegrated(g, weights, fixed);
			
			//transfer the weights of the original graph to the neighborhood graph
			EdgeMap neighborWeights = neighborhood.createEdgeMap();
			
			for(EdgeCursor ec = neighborhood.edges(); ec.ok(); ec.next()){
				Edge edge = ec.edge();
				Edge origEdge = (Edge) neighborhood.getEdgeValue(edge);
				neighborWeights.setDouble(edge, weights.getDouble(origEdge));
			}
			
			//each edge list refers edges in the neighborhood graph
			ArrayList<EdgeList> allMitsInNeighborhood = allMSTs(neighborhood, neighborWeights);
				
			//convert to an edgelist in the original edges
			for(EdgeList list: allMitsInNeighborhood){
					
				EdgeList origEdges = new EdgeList();
					
				//recover the original edges
				for(EdgeCursor ec = list.edges(); ec.ok(); ec.next()){
					Edge edge = ec.edge();
					Edge origEdge = (Edge) neighborhood.getEdgeValue(edge);
					origEdges.add(origEdge);
				}
					
				removeNotFixedLeaves(origEdges, fixed);
				
				//add the edge list to result if the edgeList is not in the result yet.
				if(!containsEdgeList(result, origEdges))
					result.add(origEdges);
			}		
		}
		
		return result;
	}

	// get a neighborhood graphs of the set of fixed node which may
	// contain extra nodes because the shortest paths may go
	// through extra nodes. The neighborhood graph is created from the complete graph
	//using the shortest path in the original graph between a pair of nodes.
	private static ValuedGraph neighborhoodGraphIntegrated(ValuedGraph g, EdgeMap weights,
			Collection<Node> fixed) {
		
		// map from a node of the fixed nodes to all the shortest paths 
		//to all the nodes in the collection of fixed.
		HashMap<Node, HashMap<Node, ArrayList<EdgeList>>> paths = new 
			HashMap<Node, HashMap<Node, ArrayList<EdgeList>>>();
		
		
		ValuedGraph complete = new ValuedGraph();
		
		Iterator<Node> fixedIt = fixed.iterator();
		while (fixedIt.hasNext()) {
			
			Node v = fixedIt.next();
			Node nv = complete.createNode();
			complete.putNodeValue(nv, v);
			
			//get all the shortest paths from the v to all the nodes in the collection of fixed.
			HashMap<Node, ArrayList<EdgeList>> shortestPaths = allShortestPaths(g, v,
					fixed, weights);
			
			paths.put(v, shortestPaths);
		}


		makeEdgesForNeighborhoodGraphIntegrated(g, complete, paths);


		return complete;
	}

	
	// create the edges of the complete graph through the shortest paths;
	private static void makeEdgesForNeighborhoodGraphIntegrated(ValuedGraph g, ValuedGraph complete, 
			HashMap<Node, HashMap<Node, ArrayList<EdgeList>>> paths) {
		
		System.out.println("starting makeEdgesForNeighborhoodGraph.");
		
		// make a map from the original graph nodes to complete graph nodes.
		HashMap<Node, Node> origToComplete = new HashMap<Node, Node>();
		
		// a container remembering which edge has been used in some paths.
		ArrayList<Edge> visitedEdges = new ArrayList<Edge>();

		for(NodeCursor nc = complete.nodes(); nc.ok(); nc.next()){
			Node aNode = nc.node();
			Node origNode = (Node) complete.getNodeValue(aNode);
			origToComplete.put(origNode, aNode);
		}
		
		// for pair of node in complete make edges, plus possible new nodes.
		Node[] compNodeArray = complete.getNodeArray();
		for (int i = 0; i < compNodeArray.length; i++) {
			Node source = compNodeArray[i];
			HashMap<Node, ArrayList<EdgeList>> sourcePaths = paths.get(complete
					.getNodeValue(source));
			for (int j = i + 1; j < compNodeArray.length; j++) {
				
				Node target = compNodeArray[j];
				
				ArrayList<EdgeList> sourceToTarget = sourcePaths.get(complete
						.getNodeValue(target));
				
				for(EdgeList aPath: sourceToTarget){
					
					for (EdgeCursor ec = aPath.edges(); ec.ok(); ec.next()) {
						
						Edge edge = ec.edge();
						
						if (!visitedEdges.contains(edge)) {
							
							visitedEdges.add(edge);
							
							Node edgeSource = edge.source();
							Node edgeTarget = edge.target();
							
							Node compEdgeSource, compEdgeTarget;
							if (origToComplete.get(edgeSource) != null)
								compEdgeSource = (Node) origToComplete
										.get(edgeSource);
							else {
								
								compEdgeSource = complete.createNode();
								
								complete.putNodeValue(compEdgeSource,
										edgeSource);
								
								origToComplete.put(edgeSource, compEdgeSource);	
							}
							if (origToComplete.get(edgeTarget) != null)
								compEdgeTarget = (Node) origToComplete
										.get(edgeTarget);
							else {
								
								compEdgeTarget = complete.createNode();
								
								complete.putNodeValue(compEdgeTarget,
										edgeTarget);
								
								origToComplete.put(edgeTarget, compEdgeTarget);
							}
							
							Edge compEdge = complete.createEdge(compEdgeSource,
									compEdgeTarget);
							
							complete.putEdgeValue(compEdge, edge);
						}//if visitedEdges
					}//for each edge in a path
				}//for a path
			}//for a target node	
		}//for a source node
		
			
		System.out.println("End makeNeighborHood.");
		
	}
	
	
	/**
	 * remove the nodes that are leaves but not fixed.
	 * 
	 * @param origEdges
	 */
	public static void removeNotFixedLeaves(EdgeList origEdges, Collection<Node> fixed){
		
		HashMap<Node, ArrayList<Edge>> node2edges = new HashMap<Node, ArrayList<Edge>>();
		
		for(EdgeCursor ec = origEdges.edges(); ec.ok(); ec.next()){
			
			Edge edge = ec.edge();
			
			Node source = edge.source();
			if(node2edges.get(source) != null)
				node2edges.get(source).add(edge);
			else{
				ArrayList<Edge> edges = new ArrayList<Edge>();
				edges.add(edge);
				node2edges.put(source, edges);
			}
			
			Node target = edge.target();
			if(node2edges.get(target) != null)
				node2edges.get(target).add(edge);
			else{
				ArrayList<Edge> edges = new ArrayList<Edge>();
				edges.add(edge);
				node2edges.put(target, edges);
			}	
		}
		
		Iterator<Node> it = node2edges.keySet().iterator();
		while(it.hasNext()){
			Node key = it.next();
			
			ArrayList<Edge> edges = node2edges.get(key);
			
			if(edges.size() == 1 && !fixed.contains(key)){
				origEdges.remove(edges.get(0));
			}
		}
	}

	
	/**
	 * get all steiner trees by the set of fixed nodes.
	 * 
	 * @param Graph
	 *            g
	 * @param EdgeMap
	 *            weights
	 * @param ArrayList
	 *            fixed
	 * @return a list of EdgeLiss each of which represents a Steiner tree
	 */
	public static ArrayList<EdgeList> allSteinerTrees(ValuedGraph g, EdgeMap weights,
			Collection<Node> fixed) {

		ArrayList<EdgeList> result = new ArrayList<EdgeList>();
		
		if (fixed.isEmpty() || fixed.size() == 1)
			return result;
		else {
			
			//get all the neighborhood graphs
			ArrayList<ValuedGraph> neighborhoodGraphs = neighborhoodGraph(g, weights, fixed);
			
			//for each neighborhood graph, get all MSTs
			for(ValuedGraph neighborhood: neighborhoodGraphs){
				
				//transfer the weights of the original graph to the neighborhood graph
				EdgeMap neighborWeights = neighborhood.createEdgeMap();
				
				for(EdgeCursor ec = neighborhood.edges(); ec.ok(); ec.next()){
					Edge edge = ec.edge();
					Edge origEdge = (Edge) neighborhood.getEdgeValue(edge);
					neighborWeights.setDouble(edge, weights.getDouble(origEdge));
				}
				
				//each edge list refers edges in the neighborhood graph
				ArrayList<EdgeList> allMitsInNeighborhood = allMSTs(neighborhood, neighborWeights);
				
				//convert to an edgelist in the original edges
				for(EdgeList list: allMitsInNeighborhood){
					
					EdgeList origEdges = new EdgeList();
					
					//recover the original edges
					for(EdgeCursor ec = list.edges(); ec.ok(); ec.next()){
						Edge edge = ec.edge();
						Edge origEdge = (Edge) neighborhood.getEdgeValue(edge);
						origEdges.add(origEdge);
					}
					
					//add the edge list to result if the edgeList is not in the result yet.
					if(!containsEdgeList(result, origEdges))
						result.add(origEdges);
				}
			}
			
		}
		
		return result;
	}

	// get a set of neighborhood graphs of the set of fixed node which may
	// contain extra nodes because the shortest paths may go
	// through extra nodes. Each neighborhood graph is created from the complete graph
	//using the shortest path in the original graph between a pair of nodes.
	private static ArrayList<ValuedGraph> neighborhoodGraph(ValuedGraph g, EdgeMap weights,
			Collection<Node> fixed) {
		
		// map from a node of the fixed nodes to all the shortest paths 
		//to all the nodes in the collection of fixed.
		HashMap<Node, HashMap<Node, ArrayList<EdgeList>>> paths = new 
			HashMap<Node, HashMap<Node, ArrayList<EdgeList>>>();
		
		ArrayList<ValuedGraph> allGraphs = new ArrayList<ValuedGraph>();
		
		ValuedGraph complete = new ValuedGraph();
		
		Iterator<Node> fixedIt = fixed.iterator();
		while (fixedIt.hasNext()) {
			
			Node v = fixedIt.next();
			Node nv = complete.createNode();
			complete.putNodeValue(nv, v);
			
			//get all the shortest paths from the v to all the nodes in the collection of fixed.
			HashMap<Node, ArrayList<EdgeList>> shortestPaths = allShortestPaths(g, v,
					fixed, weights);
			
			paths.put(v, shortestPaths);
		}

		//get the combinations of the shortest paths
		ArrayList<HashMap<Node, HashMap<Node, EdgeList>>> pathCombis = 
			getPathCombinations(paths);
		
		for(HashMap<Node, HashMap<Node, EdgeList>> shortestPaths: pathCombis){
			
			ValuedGraph completeCopy = complete.makeCopy();
			makeEdgesForNeighborhoodGraph(g, completeCopy, shortestPaths);
			
			if(!containsGraph(allGraphs, completeCopy))
				allGraphs.add(completeCopy);
			
		}

		return allGraphs;
	}

	// create the edges of the complete graph through the shortest paths;
	private static void makeEdgesForNeighborhoodGraph(ValuedGraph g, ValuedGraph complete, 
			HashMap<Node, HashMap<Node, EdgeList>> paths) {
		
		System.out.println("starting makeEdgesForNeighborhoodGraph.");
		
		// make a map from the original graph nodes to complete graph nodes.
		HashMap<Node, Node> origToComplete = new HashMap<Node, Node>();
		
		// a container remembering which edge has been used in some paths.
		ArrayList<Edge> visitedEdges = new ArrayList<Edge>();

		for(NodeCursor nc = complete.nodes(); nc.ok(); nc.next()){
			Node aNode = nc.node();
			Node origNode = (Node) complete.getNodeValue(aNode);
			origToComplete.put(origNode, aNode);
		}
		
		// for pair of node in complete make edges, plus possible new nodes.
		Node[] compNodeArray = complete.getNodeArray();
		for (int i = 0; i < compNodeArray.length; i++) {
			Node source = compNodeArray[i];
			HashMap<Node, EdgeList> sourcePaths = paths.get(complete
					.getNodeValue(source));
			for (int j = i + 1; j < compNodeArray.length; j++) {
				
				Node target = compNodeArray[j];
				
				EdgeList sourceToTarget = sourcePaths.get(complete
						.getNodeValue(target));
				
				for (EdgeCursor ec = sourceToTarget.edges(); ec.ok(); ec.next()) {
					
					Edge edge = ec.edge();
					
					if (!visitedEdges.contains(edge)) {
						
						visitedEdges.add(edge);
						
						Node edgeSource = edge.source();
						Node edgeTarget = edge.target();
						
						Node compEdgeSource, compEdgeTarget;
						if (origToComplete.get(edgeSource) != null)
							compEdgeSource = (Node) origToComplete
									.get(edgeSource);
						else {
							
							compEdgeSource = complete.createNode();
							
							complete.putNodeValue(compEdgeSource,
									edgeSource);
							
							origToComplete.put(edgeSource, compEdgeSource);	
						}
						if (origToComplete.get(edgeTarget) != null)
							compEdgeTarget = (Node) origToComplete
									.get(edgeTarget);
						else {
							
							compEdgeTarget = complete.createNode();
							
							complete.putNodeValue(compEdgeTarget,
									edgeTarget);
							
							origToComplete.put(edgeTarget, compEdgeTarget);
						}
						
						Edge compEdge = complete.createEdge(compEdgeSource,
								compEdgeTarget);
						
						complete.putEdgeValue(compEdge, edge);
					}
				}
			}
			
		}
		
		//associate the nodes and edges of the new graph with the values of the nodes and edges
		//in the original graph
		//don't need to do that here! All Steiner trees are edge lists of original edges
		/*
		for(NodeCursor nc = complete.nodes(); nc.ok(); nc.next()){
			Node node = nc.node();
			Node origNode = (Node)complete.getNodeValue(node);
			complete.putNodeValue(node, g.getNodeValue(origNode));
		}
		
		for(EdgeCursor ec = complete.edges(); ec.ok(); ec.next()){
			Edge edge = ec.edge();
			Edge origEdge = (Edge) g.getEdgeValue(edge);
			complete.putEdgeValue(edge, g.getEdgeValue(origEdge));
			
		}
		*/
			
		System.out.println("End makeNeighborHood.");
		
	}
	
	
	//get the combinations of the shortest paths
	private static ArrayList<HashMap<Node, HashMap<Node, EdgeList>>> getPathCombinations(
			HashMap<Node, HashMap<Node, ArrayList<EdgeList>>> paths){
		
		ArrayList<HashMap<Node, HashMap<Node, EdgeList>>> result = new 
		ArrayList<HashMap<Node, HashMap<Node, EdgeList>>>();
		
		//get the list of keys in the given map
		ArrayList<Node> outKeys = new ArrayList<Node>();
		outKeys.addAll(paths.keySet());
		
		//outer list of lists: each inner list is a combination of the shortest paths for a outkey node
		ArrayList<ArrayList<HashMap<Node, EdgeList>>> listOfInnerCombi = new ArrayList<ArrayList<HashMap<Node, EdgeList>>>();
		
		for(Node outNode: outKeys){
			HashMap<Node, ArrayList<EdgeList>> outValue = paths.get(outNode);
			
			//get the list of keys of the inner map
			ArrayList<Node> innerKeys = new ArrayList<Node>();
			innerKeys.addAll(outValue.keySet());
			
			//inner list of lists: the inner ArrayList contains the shortest paths for a single node
			ArrayList<ArrayList<EdgeList>> innerPaths = new ArrayList<ArrayList<EdgeList>>();
			
			for(Node innerNode: innerKeys){
				innerPaths.add(outValue.get(innerNode));
			}
			
			//get combination: the inner ArrayList contains a combination of the shortest paths for 
			//all the nodes.
			ArrayList<ArrayList<EdgeList>> innerCombi = getCombination(innerPaths);
			
			//create map from the inner combination
			ArrayList<HashMap<Node, EdgeList>> innerCombiMap = new ArrayList<HashMap<Node, EdgeList>>();
			for(ArrayList<EdgeList> list: innerCombi){
				HashMap<Node, EdgeList> node2path = new HashMap<Node, EdgeList>();
				for(int i = 0; i < innerKeys.size(); i++){
					//the elements in innerKeys and list is in one-to-one correspondence. It should be!!
					node2path.put(innerKeys.get(i), list.get(i));
				}
				innerCombiMap.add(node2path);
			}
			
			listOfInnerCombi.add(innerCombiMap);
		}
		
		//get combination: the inner ArrayList contains a combination of all the shortest paths from each 
		//outkey node
		ArrayList<ArrayList<HashMap<Node, EdgeList>>> outerCombi = getCombination(listOfInnerCombi);
		
		//create map from the outer combination
		for(ArrayList<HashMap<Node, EdgeList>> list: outerCombi){
			HashMap<Node, HashMap<Node, EdgeList>> node2allPaths = new HashMap<Node, HashMap<Node, EdgeList>>();
			for(int i = 0; i < outKeys.size(); i++){
				node2allPaths.put(outKeys.get(i), list.get(i));
			}
			
			result.add(node2allPaths);
		}
		
		return result;
	}
	
	//the input is an ArrayList of ArrayLists; the output is the combination
	//of the elements of the ArrayLists: for example, input is: 
	//[1,2] and [a,b,c], then the output is: [1,a],[1,b],[1,c],[2,a],[2,b],[2,c].
	public static ArrayList getCombination(ArrayList aSetOfSets){
		ArrayList result=new ArrayList();
		
		System.out.println("%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%");
		System.out.println("GraphAglo: getCombination: The Number of Combinations will be:");
		System.out.println("There are " + aSetOfSets.size() + " lists. The sizes of the lists are:");
		int prod  = 1;
		
		for(int i = 0; i < aSetOfSets.size(); i++){
			ArrayList list = (ArrayList)aSetOfSets.get(i);
			System.out.println("list " + i + ", size: " + list.size());
			prod *= list.size();
		}
		
		System.out.println("The number of combinations is " + prod);
		System.out.println("%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%");
		
		//if(prod > 500000)
			//return result;
		
		if(aSetOfSets.size()==0)
			return result;
			
		ArrayList sofar=new ArrayList();
		int level=0;
		
		getCombinationRecursive(result,aSetOfSets,sofar,level);	
	
		return result;
	}
	
	private static void getCombinationRecursive(ArrayList result,
	 ArrayList aSetOfSets, ArrayList sofar,int level){
		//if reached the last level, add elements of last level
		if(level==aSetOfSets.size()-1){
			ArrayList lastSet=(ArrayList)aSetOfSets.get(level);
			for(int i=0;i<lastSet.size();i++){
				ArrayList atlast=new ArrayList();
				atlast.addAll(sofar);
				atlast.add(lastSet.get(i));
				result.add(atlast);
					return;
			}
		}
		else{
			ArrayList curSet=(ArrayList)aSetOfSets.get(level);
			for(int j=0;j<curSet.size();j++){
				ArrayList newSofar=new ArrayList();
				newSofar.addAll(sofar);
				newSofar.add(curSet.get(j));
				getCombinationRecursive(result,aSetOfSets,
				newSofar,level+1);
			}
		}
	}

	
	/**
	 * 
	 * Check whether the graph is in the list of graphs
	 * 
	 * @param allGraphs
	 * @param graph
	 * @return
	 */
	private static boolean containsGraph(ArrayList<ValuedGraph> allGraphs, ValuedGraph graph){
		
		for(ValuedGraph existingGraph: allGraphs){
			if(sameGraph(existingGraph, graph))
					return true;
		}
				
		return false;
	}
		
	private static boolean sameGraph(ValuedGraph first, ValuedGraph second){
		
		Edge[] firstEdges = first.getEdgeArray();
		Edge[] secondEdges = second.getEdgeArray();
		
		ArrayList<Edge> firstOrigEdges = new ArrayList<Edge>();
		ArrayList<Edge> secondOrigEdges = new ArrayList<Edge>();
		
		for (int i = 0; i < firstEdges.length; i++)
			firstOrigEdges.add((Edge) first.getEdgeValue(firstEdges[i]));

		for (int i = 0; i < secondEdges.length; i++) {
			Edge value = (Edge) second.getEdgeValue(secondEdges[i]);
			secondOrigEdges.add(value);
			
			if(!firstOrigEdges.contains(value))
				return false;
		}
			
		for(Edge value: firstOrigEdges){
			if (!secondOrigEdges.contains(value)) 
				return false;
		}
		
		return true;
	}
	
	
	/**
	 * check if the set of MSTs contains the given MST
	 * 
	 */
	private static boolean containsEdgeList(ArrayList<EdgeList> mists, EdgeList mst){
		
		for(EdgeList existingMST: mists){
			
			if(sameMSTs(existingMST, mst))
				return true;
		}
		
		return false;
	}

}

/**
 * Comparator for comparing two edges according their weights.
 * 
 */
class EdgeComparator implements Comparator<Edge> {
	private EdgeMap weights;

	public EdgeComparator(EdgeMap weights) {
		this.weights = weights;
	}

	public int compare(Edge e1, Edge e2) {
		double w1 = weights.getDouble(e1);
		double w2 = weights.getDouble(e2);

		if (w1 <= w2)
			return -1;
		return 1;
	}
}
